﻿#include "stdafx.h"
#include "DiameterOfBinaryTree.h"
#include <iostream>

using namespace std;

namespace algorithm {
int CDiameterOfBinaryTree::GetDiameter(TreeNode *root)
{
    if (!root) {
        return 0;
    }

    int diameter = 0;
    int leftHeight = GetTreeNodeHeight(root, diameter);
    //cout << "diameter: " << diameter << endl;

    return diameter;
}

int CDiameterOfBinaryTree::GetTreeNodeHeight(TreeNode* root, int& maxDiameter)
{
    if (!root) {
        return 0;
    }
    if (!root->left && !root->right) {
        return 0;
    }
    int leftHeight = GetTreeNodeHeight(root->left, maxDiameter);
    int rightHeight = GetTreeNodeHeight(root->right, maxDiameter);
    int diameter = 0;
    if (root->left) {
        diameter += (leftHeight + 1);
    }
    if (root->right) {
        diameter += (rightHeight + 1);
    }
    maxDiameter = max(diameter, maxDiameter);
    return max(leftHeight, rightHeight) +1;
}

}
